#include <iostream>
#include <vector>
#include <string>
#include <string.h>


using namespace std;
// 第n个太波那契数列
class Solution
{
public:
    int tribonacci(int n)
    {
        // 空间优化,O(n) -> O(1)
        if (n == 0)
            return 0; // 处理边界情况，防止越界，保证下面状态转移方程不会越界（i-3）
        if (n == 1)
            return 1;
        if (n == 2)
            return 1;
        int a = 0, b = 1, c = 1, d = 0;
        for (size_t i = 3; i <= n; ++i)
        {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
    // int tribonacci(int n)
    // {
    //     // 1、创建dp表
    //     // 2、完成初始化
    //     // 3、填满dp表
    //     // 4、返回值
    //     if(n==0) return 0;// 处理边界情况，防止越界，保证下面状态转移方程不会越界（i-3）
    //     if(n==1) return 1;
    //     if(n==2) return 1;
    //     vector<int> dp(n+1);//从0开始，那么n+1表示第n个数
    //     dp[0]=0;
    //     dp[1]=1;
    //     dp[2]=1;
    //     for(size_t i=3;i<=n;++i)
    //     {
    //         dp[i] = dp[i-1]+dp[i-2]+dp[i-3];//状态转移方程
    //     }
    //     return dp[n];
    // }
};

// 三步问题
class Solution
{
public:
    int waysToStep(int n)
    {
        static const long int NUM = 1000000007;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        if (n == 3)
            return 4;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % NUM + dp[i - 3]) % NUM;
        }
        return dp[n];
    }
};

// 最小花费爬楼梯
class Solution
{
public:
    int minCostClimbingStairs(vector<int> &cost)
    {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; ++i)
        {
            // 我现在在i位置，因为可以向上爬1（i-1）或者2个阶梯（i-2），所以说最小花费就是i-1和i-2的花费小的值
            // dp[i-1]+cost[i-1] ： dp[i-1]就是我从0到i-1位置的最小花费，加上我cost[i-1]也就是i-1位置爬到i位置消耗的体力值
            // dp[i-2]+cost[i-2] ： dp[i-2]就是我从0到i-2位置的最小花费，加上我cost[i-2]也就是i-2位置爬到i位置消耗的体力值
            // 然后dp[i-1]+cost[i-1]和dp[i-2]+cost[i-2]的最小值，就表示从0爬到i位置的最小花费值
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};
// 解码方法
class Solution
{
public:
    int numDecodings(string s)
    {
        int n = s.size();
        vector<int> dp(n); // 末尾下标就是n-1
        // dp[0] = s[0] != '0';// 第一个数不能为字符0，不然没有解码方法
        if (s[0] == '0')
            return 0;
        dp[0] = 1; // 如果s[0]不等于字符0，那么就表示dp[0]的解码方法就有一种了（只有1或者0，因为第一个数据前面没有数据和它结合）
        if (n == 1)
            return dp[0]; // 如果字符串就只有一个字符，那么直接返回，不然下面i-2越界了

        // dp数组第二个位置存储的方法个数
        if (s[0] != '0' && s[1] != '0') // 情况1 ： 如果s[0]和s[1]位置都能单独解码，那么dp[1]位置的解码方法+1
            dp[1] += 1;
        // sum的范围应该是【10,26】，如果小于10，那么s[0]位置为0，就表示没有解码方法
        int sum = (s[0] - '0') * 10 + (s[1] - '0');
        if (10 <= sum && sum <= 26) // 情况2 ： s[0]与s[1]相结合进行运算，如果结果是10到26，表示结合成功，那么dp[1]位置的解码方法又+1
            dp[1] += 1;

        for (int i = 2; i < n; ++i) // 对后面2到n-1下标位置的dp数组进行填表
        {
            if (s[i] != '0')
                dp[i] += dp[i - 1];
            int sum = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (10 <= sum && sum <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[n - 1]; // n-1就是对应dp数组的最后一个位置，也是解码成功的全部方法的集合
    }
};